1 基本概念

1.1 定义

设

• ${\displaystyle Q=\{q_1,\cdots ,q_N\}}$ 是所有可能状态的集合, ${\displaystyle V=\{v_1,\cdots ,v_M\}}$ 是所有可能的观测的集合
• 在时间长度 ${\displaystyle T}$ 下有状态序列 ${\displaystyle I=(i_1,\cdots ,i_T)}$ 和观测序列 ${\displaystyle O=(o_1,\cdots ,o_T)}$
• 状态转移矩阵 ${\displaystyle A=[a_{ij}{]}_{N\times N}}$, 其中 ${\displaystyle a_{ij}=\mathbb{P}(i_{t+1}=q_j|i_t=q_i),1\le i,j\le N}$^[1]
• 观测概率矩阵 ${\displaystyle B=[b_j(k){]}_{N\times M}}$, 其中 ${\displaystyle b_j(k)=\mathbb{P}(o_t=v_k|i_t=q_j)}$, ${\displaystyle 1\le k\le M}$, ${\displaystyle 1\le j\le N}$.
• 初始状态概率向量 ${\displaystyle \pi =({\pi }_i)}$, 其中 ${\displaystyle {\pi }_i=\mathbb{P}(i_1=q_i),i=1,\cdots ,N}$ 是 ${\displaystyle t=1}$ 时处于状态 ${\displaystyle q_i}$ 的概率.

因此隐 Markov 模型由 ${\displaystyle \lambda =(A,B,\pi )}$ 决定, 其中 ${\displaystyle \pi ,A}$ 决定状态序列, ${\displaystyle B}$ 决定观测序列.

隐 Markov 模型的两个基本假设:

1. 齐次 Markov 性假设: $$\mathbb{P}(i_t|i_{t-1},o_{t-1},\cdots ,i_1,o_1)=\mathbb{P}(i_t|i_{t-1}),\mathrm{\forall }t.$$
2. 观测独立性假设: $$\mathbb{P}(o_t|i_{1\le t^{\prime }\le T},o_{t^{\prime }\ne t})=\mathbb{P}(o_t|i_t).$$

1.2 观测序列的生成过程

1.3 个基本问题

• 概率计算问题: 计算 ${\displaystyle \mathbb{P}(O|\lambda )}$
• 学习问题: 估计参数 ${\displaystyle \lambda =(A,B,\lambda )}$, 使 ${\displaystyle \mathbb{P}(O|\lambda )}$ 最大
• 预测问题(解码问题): 估计状态序列 ${\displaystyle I}$, 使 ${\displaystyle \mathbb{P}(I|O)}$ 最大

2 概率计算算法

2.1 直接计算

直接计算各个概率: 对 ${\displaystyle I=(i_1,\cdots ,i_T)}$, ${\displaystyle O=(o_1,\cdots ,o_T)}$, $$\mathbb{P}(I|\lambda )={\pi }_{i_1}{a}_{i_1{i}_2}\cdots a_{i_{T-1}{i}_T},$$ $$\mathbb{P}(O|I,\lambda )=b_{i_1}(o_1)\cdots b_{i_T}(o_T),$$ 从而 $$\mathbb{P}(O,I|\lambda )=\mathbb{P}(O|I,\lambda )\mathbb{P}(I|\lambda ),$$ 最后对 ${\displaystyle I}$ 求和: $$\mathbb{P}(O|\lambda )=\sum _I\mathbb{P}(O|I,\lambda )\mathbb{P}(I|\lambda )=\sum _{i_1,\cdots ,i_T}{\pi }_{i_1}\prod _{j=1}^{T-1}{b}_{i_j}(o_j)a_{i_j{i}_{j+1}}\cdot b_{i_T}(o_T).$$ 这个公式是 ${\displaystyle O(T{N}^T)}$ 阶的, 计算量过大.

2.2 前向算法

关于第二步, 根据定义 ${\displaystyle \sum _{j=1}^N{\alpha }_t(j)a_{ij}=\mathbb{P}(o_1,\cdots ,o_t,i_{t+1}=q_i|\lambda )}$, 然后再乘上 ${\displaystyle b_i(o_{t+1})}$ 就是 ${\displaystyle {\alpha }_{t+1}(i)}$. 第三步由定义容易得到.

在每个时刻 ${\displaystyle t=1,\cdots ,T-1}$, 都计算 ${\displaystyle {\alpha }_{t+1}(i)}$ 的 ${\displaystyle N}$ 个值, 可以直接利用之前的 ${\displaystyle {\alpha }_t(j)}$, 避免重复计算, 这样计算量从 ${\displaystyle O(T{N}^T)}$ 下降到了 ${\displaystyle O(N^{2}T)}$.

2.3 后向算法

根据前向和后向概率, 可以统一 $$\mathbb{P}(O|\lambda )=\sum _{i=1}^N\sum _{j=1}^N{\alpha }_t(i)a_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j),1\le t\le T-1.$$

2.4 一些概率与期望的计算

1. 记 ${\displaystyle {\gamma }_t(i)=\mathbb{P}(i_t=q_i|O,\lambda )}$. 事实上 $${\gamma }_t(i)=\frac{\mathbb{P}(i_t=q_i,O|\lambda )}{\mathbb{P}(O|\lambda )}=\frac{{\alpha }_t(i){\beta }_t(i)}{\mathbb{P}(O|\lambda )}=\frac{{\alpha }_t(i){\beta }_t(i)}{\sum _{j=1}^N{\alpha }_t(j){\beta }_t(j)}.$$

2. 记 ${\displaystyle {\xi }_t(i,j)=\frac{\mathbb{P}(i_t=q_i,i_{t+1}=q_j,O|\lambda )}{\mathbb{P}(O|\lambda )}}$, 则 $${\xi }_t(i,j)=\frac{{\alpha }_t(i)a_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)}{\sum _{i=1}^N\sum _{j=1}^N{\alpha }_t(i)a_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)}.$$

3. 基于 ${\displaystyle {\gamma }_t(i),{\xi }_t(i,j)}$ 得到的期望值:

   1. ${\displaystyle O}$ 下 ${\displaystyle i}$ 出现的期望: ${\displaystyle \sum _{t=1}^T{\gamma }_t(i)}$.
   2. ${\displaystyle O}$ 下 ${\displaystyle i}$ 转移的期望: ${\displaystyle \sum _{t=1}^{T-1}{\gamma }_t(i)}$.
   3. ${\displaystyle O}$ 下 ${\displaystyle i}$ 转移到 ${\displaystyle j}$ 的期望: ${\displaystyle \sum _{t=1}^{T-1}{\xi }_t(i,j)}$.

3 学习算法

3.1 监督学习算法

假设知道 ${\displaystyle S}$ 个长度相同的序列: ${\displaystyle \{(O_1,I_1),\cdots ,(O_S,I_S)\}}$. 可以用极大似然估计来估计模型的参数.

1. 转移概率 ${\displaystyle a_{ij}}$:
   假设 ${\displaystyle t}$ 下状态为 ${\displaystyle i}$, ${\displaystyle t+1}$ 下状态为 ${\displaystyle j}$ 的频数为 ${\displaystyle A_{ij}}$, 则 $${\hat{a}}_{ij}=\frac{A_{ij}}{\sum _{j=1}^N{A}_{ij}},1\le i,j\le N.$$
2. 观测概率 ${\displaystyle b_j(k)}$:
   设状态为 ${\displaystyle j}$ 且观测为 ${\displaystyle k}$ 的频数为 ${\displaystyle B_{jk}}$, 则 $${\hat{b}}_j(k)=\frac{B_{jk}}{\sum _{k=1}^M{B}_{jk}},1\le j\le N,1\le k\le M.$$
3. ${\displaystyle {\hat{\pi }}_i}$: 初始状态下 ${\displaystyle q_i}$ 的频率.

3.2 Baum-Welch 算法

人工标注数据的代价很高, 因此采用无监督学习的算法.
现在只给定 ${\displaystyle \{O_1,\cdots ,O_S\}}$. 将观测序列看作 ${\displaystyle O}$, 状态序列看作不可观测的 ${\displaystyle I}$, 则隐 Markov 模型为 $$\mathbb{P}(O|\lambda )=\sum _I\mathbb{P}(O|I,\lambda )\mathbb{P}(I|\lambda ).$$ 可以用 EM算法 实现.

1. E 步: 计算 ${\displaystyle Q(\lambda ,\bar{\lambda })}$: $$Q(\lambda ,\bar{\lambda })=\sum _I\log \mathbb{P}(O,I|\lambda )\mathbb{P}(O,I|\bar{\lambda }).$$ 带入 $$\mathbb{P}(O,I|\lambda )={\pi }_{i_1}{b}_{i_{{}_1}}(o_1)a_{i_1{i}_2}{b}_{i_2}(o_2)\cdots a_{i_{T-1}{i}_T}{b}_{i_T}(o_T),$$ 有$$\begin{array}{rl}Q(\lambda ,\bar{\lambda })=& \sum _I\log {\pi }_{i_1}\mathbb{P}(O,I|\bar{\lambda })+\sum _I(\sum _{t=1}^{T-1}\log a_{i_t{i}_{t+1}})\mathbb{P}(O,I|\bar{\lambda })\\ & +\sum _I(\sum _{t=1}^T\log b_{i_t}(o_t))\mathbb{P}(O,I|\bar{\lambda }).\end{array}$$
2. M 步: 极大化 ${\displaystyle Q(\lambda ,\bar{\lambda })}$, 求参数 ${\displaystyle A,B,\pi }$. 注意到 ${\displaystyle \pi ,A,B}$ 分别出现在上面的三项中, 因此可以分别极大化. 对第一项, 结合 ${\displaystyle \sum _{i=1}^N{\pi }_i=1}$, 写出 Lagrange 函数 $$\sum _{i=1}^N\log {\pi }_i\mathbb{P}(O,i_1=i|\bar{\lambda })+\gamma (\sum _{i=1}^N{\pi }_i-1).$$ 对 ${\displaystyle {\pi }_i}$ 求偏导让结果为 ${\displaystyle 0}$, 得 $${\pi }_i=\frac{\mathbb{P}(O,i_1=i|\bar{\lambda })}{\mathbb{P}(O|\bar{\lambda })}.$$
   类似地, 第二项可以写为 $$\sum _{i=1}^N\sum _{j=1}^N\sum _{t=1}^{T-1}\log a_{ij}\mathbb{P}(O,i_t=i,i_{t+1}=j|\bar{\lambda }).$$ 结合约束条件 ${\displaystyle \sum _{j=1}^N{a}_{ij}=1}$, 类似得 $$a_{ij}=\frac{\sum _{t=1}^{T-1}\mathbb{P}(O,i_t=i,i_{t+1}=j|\bar{\lambda })}{\sum _{t=1}^{T-1}\mathbb{P}(O,i_t=i|\bar{\lambda })}.$$
   最后对第三项 $$\sum _{j=1}^N\sum _{t=1}^T\log b_j(o_t)\mathbb{P}(O,i_t=j|\bar{\lambda }),$$ 结合 ${\displaystyle \sum _{k=1}^M{b}_j(k)=1}$, 注意要添加限定条件 ${\displaystyle o_t=v_k}$, 则 $$b_j(k)=\frac{\sum _{t=1}^T\mathbb{P}(O,i_t=j|\bar{\lambda })\mathbf{1}\{o_t=v_k\}}{\sum _{t=1}^T\mathbb{P}(O,i_t=j|\bar{\lambda })}.$$
   结合 gamma 和 xi, 有 $$\begin{array}{}\text{(3.1)}& a_{ij}=\frac{\sum _{t=1}^{T-1}{\xi }_t(i,j)}{\sum _{t=1}^{T-1}{\gamma }_t(i)},b_j(k)=\frac{\sum _{t=1,o_t=v_k}^T{\gamma }_t(j)}{\sum _{t=1}^T{\gamma }_t(j)},{\pi }_i={\gamma }_1(i).\end{array}$$

预测算法